第52章 完全二叉树和二叉排序树

完全二叉树和二叉排序树是两种具有特殊性质的二叉树，在数据存储和查找领域应用广泛。完全二叉树因其结构规整，适合高效的数组存储和层次遍历；二叉排序树则通过定义节点间的有序关系，支持高效的动态查找、插入和删除操作。

52.1 完全二叉树

52.1.1 定义与结构特性

完全二叉树是一种特殊的二叉树，其结构满足： 除最后一层外，其余各层的节点数均达到最大值，即第$i$层有$2^{i-1}$个节点，$i ≥ 1$。 最后一层的节点从左到右连续排列，且不存在右边的节点无左兄弟的情况（即若最后一层有缺失节点，缺失的节点只能在右侧）。

示例： 深度为$3$的完全二叉树：第$1$层$1$个节点，第$2$层$2$个节点，第$3$层最多$4$个节点（若最后一层有$3$个节点，则必须是左起前$3$个）。 非完全二叉树：最后一层的节点不连续（如第$3$层有节点但中间存在空缺），或非最后一层的节点数未达最大值。

52.1.2 性质

节点编号特性：若对完全二叉树的节点按层次顺序（从根节点开始，自上至下、自左至右）编号为$1,2,...,n$，则对任意编号为$i$的节点。

• 若$i>1$，则其父节点编号为$i/2$。
• 若$2i ≤ n$，则其左子节点编号为$2i$。
• 若$2i+1 ≤ n$，则其右子节点编号为$2i+1$。

叶子节点位置：深度为$h$的完全二叉树，叶子节点只可能在第$h$层或第$h-1$层。

节点总数与深度关系：若完全二叉树有$n$个节点，深度为$h$，则

$$h=\lfloor \log n \rfloor +1$$

叶子节点与非n - 叶子节点数量：

• 若$n$为偶数，n - 叶子节点数为$n/2$；
• 若$n$为奇数，n - 叶子节点数为$(n+1)/2$； 非n - 叶子节点数为$n - n - 叶子节点数$。

52.1.3 存储方式

完全二叉树的节点编号具有规律性，因此最适合用数组存储，无需额外存储指针，节省空间： 数组下标从$1$开始（与节点编号对应），下标$i$存储编号为$i$的节点数据。 根节点存储在下标$1$，左子节点在$2i$，右子节点在$2i+1$，父节点在$i/2$。

#define MAX_SIZE 100
//完全二叉树的数组存储
typedef struct{
int data[MAX_SIZE];//存储节点数据(下标1开始)
int n;//节点总数
} CompleteBinaryTree;

52.1.4 构造与遍历

构造：按层次顺序将节点数据填入数组即可，无需手动维护父子关系（通过编号规则自动确定）。

//初始化完全二叉树
void initCompleteBT(CompleteBinaryTree &tree, int arr[], int size){
tree.n = size;
for (int i=0;i<size;i++){
tree.data[i+1];//下标1对应第一个元素
}
}

遍历：支持二叉树的所有遍历方式（前序、中序、后序、层次），其中层次遍历可直接按数组顺序访问：

//层次遍历(按数组顺序输出)
void levelOrder (CompleteBinaryTree &tree) {
for (int i=1;i<=tree.n;i++){
printf("%d", tree.data[i]);
}
}

52.2 二叉排序树

52.2.1 定义与有序性

二叉排序树(Binary SearchTree,BST)又称二叉查找树，是一种满足以下有序性的二叉树：

1. 若左子树不为空，则左子树上所有节点的关键字均小于根节点的关键字。
2. 若右子树不为空，则右子树上所有节点的关键字均大于根节点的关键字。
3. 左、右子树本身也分别是二叉排序树（递归定义）。

特性：中序遍历二叉排序树可得到一个严格递增的关键字序列。 示例：根节点为$5$，左子树节点均小于$5$（如$3、2、4$），右子树节点均大于$5$（如$7、6、8$），中序遍历结果为$2,3,4,5,6,7,8$。

52.2.2 节点结构

二叉排序树通常采用二叉链表存储，每个节点包含数据、左子树指针和右子树指针：

//二叉排序树节点
typedef struct BSTNode {
int key;//关键字(用于比较)
struct BSTNode *left;//左子树
struct BSTNode *right;//右子树
//构造函数(C++)
BSTNode (int k): key (k), left (NULL), right (NULL) 
} BSTNode, *BSTree;

52.2.3 核心操作

52.2.3.1 查找

根据二叉排序树的有序性，查找过程类似二分查找：

1. 若树为空，查找失败。
2. 若目标值等于根节点关键字，查找成功。
3. 若目标值小于根节点关键字，递归查找左子树。
4. 若目标值大于根节点关键字，递归查找右子树。

//查找关键字为key的节点,返回节点指针(非递归实现,效率更高)
BSTNode* search (BSTree root, int key) {
while (root != NULL) {
if (root->key == key){
return root;//找到节点
} else if(key<root->key){
root=root->left;//向左子树查找
}else{
root=root->right;//向右子树查找
}
}
return NULL;//查找失败
}

52.2.3.2 插入

插入操作需保持二叉排序树的有序性，步骤如下：

1. 若树为空，直接创建新节点作为根节点。
2. 若目标值小于当前节点关键字，递归插入左子树；若左子树为空，则新节点作为左孩子。
3. 若目标值大于当前节点关键字，递归插入右子树；若右子树为空，则新节点作为右孩子。
4. 若目标值等于当前关键字，通常不插入（避免重复）。

//插入关键字key,返回新的根节点
BSTNode* insert(BSTree root, int key) {
if (root == NULL){
return new BSTNode (key);//空树,创建新节点
}
if (key <root->key){
root->left=insert(root->left,key);//插入左子树
} else if (key >root->key){
root->right=insert(root->right,key);//插入右子树
}
//相等时不插入
return root;
}

52.2.3.3 删除

删除操作需根据节点的子树情况调整，保证删除后仍有序，分三种情况：

1. 叶子节点（无左右子树）：直接删除，父指针置空。
2. 只有左/右单棵子树：删除后将子树接到父节点对应位置。
3. 同时存在左右子树：找到中序后继（右子树最小节点）或中序前驱（左子树最大节点），替换关键字后删除后继节点。

BSTNode* findMin (BSTree root){
//查找最小节点(用于找中序后继)
while (root->left!= NULL){
root = root->left;
}
return root;
}

//删除关键字为key的节点,返回新的根节点
BSTNode* remove (BSTree root, int key) {
if (root == NULL) return NULL;//树为空,无需删除
if (key<root->key){
root->left= remove (root->left,key);//左子树删除
} else if(key >root->key){
root->right= remove (root->right,key);//右子树删除
}else{
//找到待删除节点
if(root->left== NULL){//只有右子树或无子树
BSTNode *temp= root->right;
delete root;
return temp;
}else if(root->right==NULL){//只有左子树
BSTNode *temp= root->left;
delete root;
return temp;
}
//同时有左右子树,取右子树最小节点(中序后继)
BSTNode *temp = findMin (root->right);
root->key=temp->key;//替换关键字
root->right =remove (root->right,temp->key);//删除后继
}
return root;
}

52.2.4 性能分析

二叉排序树的查找、插入、删除操作的时间复杂度取决于树的高度：

1. 理想平衡树：树高为$\log n$，操作复杂度$O(\log n)$；
2. 最坏斜树（插入有序序列$1,2,3,4,5$）：退化为单链表，复杂度$O(n)$。

为规避最坏性能，工程中使用AVL树、红黑树等平衡二叉排序树，通过旋转维持平衡。

52.3 完全二叉树与二叉排序树的对比

特性	完全二叉树	二叉排序树
结构规则	层次填满，最后一层节点靠左连续	左子节点值 < 根 < 右子节点，递归有序
存储方式	数组（空间高效）、链表	二叉链表为主
核心优势	静态数据存储、父子节点快速定位	动态查找、插入、删除高效（平衡状态）
遍历特性	层次遍历最简单，中序无固定顺序	中序遍历输出严格递增序列
典型应用	堆、优先队列、数组索引结构	动态字典、数据库索引底层结构

52.4 应用场景

完全二叉树应用

1. 堆结构：堆是特殊完全二叉树，用于实现最大堆、最小堆、优先队列。
2. 数组静态二叉树：节点数量固定场景，利用下标快速访问父子节点。

二叉排序树应用

1. 动态查找表：通讯录、字典，支持实时增删查。
2. 数据库索引：B树、B+树的底层基础结构。
3. 排序辅助：中序遍历直接得到有序序列。

52.5 注意事项

完全二叉树数组存储

1. 数组下标推荐从$1$开始，简化$2i$、$2i+1$父子下标计算；
2. 需提前定义数组最大容量，防止下标越界。

二叉排序树实现

1. 连续有序数据插入会退化为斜树，性能暴跌；
2. 删除节点需区分三类情况，左右子树共存时必须处理中序后继/前驱；
3. 自定义数据类型存储关键字时，必须重载大小比较运算符。

遍历要点

1. 完全二叉树层次遍历直接遍历数组，效率最高；
2. 二叉排序核心特性为中序升序，是做题、业务开发重点。